import math


def is_prime(num):
    '''判断num大于2是否是质数'''
    if num > 2:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
    return True


primes = [2, 3]

res = {}


class NumPrimesSum:
    def __init__(self, n):
        self.num = n
        self.sumList = []
        self.sumList_num = 0

    def add_list(self, listmp):
        lisTmp = sorted(listmp)
        if lisTmp not in self.sumList:
            self.sumList.append(lisTmp)
            self.sumList_num += 1

    def __str__(self):
        return str(self.sumList)+'共有'+str(self.sumList_num)+'种'

    def __repr__(self):
        return str(self.sumList) + '共有' + str(self.sumList_num) + '种'


res[2] = NumPrimesSum(2)
res[3] = NumPrimesSum(3)
now = 4

isOK = False
while not isOK:
    if is_prime(now):
        primes.append(now)

    nowClass = NumPrimesSum(now)

    res[now] = nowClass

    limit = int(now / 2) + 1

    for n1 in range(2, limit + 1):
        n2 = now - n1
        if 1 in (n1, n2):
            continue
        n1List = res[n1].sumList
        n2List = res[n2].sumList
        if n1 in primes:
            n1List = n1List.copy()
            n1List.append([n1])
        if n2 in primes:
            n2List = n2List.copy()
            n2List.append([n2])

        if n1 in primes and n2 in primes:
            res[now].add_list([n1, n2])

        for l1 in n1List:
            tmp1 = l1.copy()
            for l2 in n2List:
                tmp = tmp1.copy()
                tmp.extend(l2)
                if sum(tmp) == now:
                    res[now].add_list(tmp)

    if res[now].sumList_num >= 5000:
        isOK = True
    print(now, res[now].sumList_num)
    now += 1
print(res[now-1])